package dynamicProgramming

// 双11购物车凑单问题

// items表示商品价格表，n表示商品个数，w表示满减条件
func DoubleAdvance(items []int, n, w int) (int, []int) {
	states := make([][]bool, n)
	for i := 0; i < len(states); i++ {
		states[i] = make([]bool, 3*w+1) // 超过满减3倍数就没必要薅羊毛了
	}
	// 特殊处理第0个物品
	states[0][0] = true
	if items[0] < 3*w {
		states[0][items[0]] = true
	}
	// 动态规划转移
	for i := 1; i < n; i++ {
		// 第i个物品不购买
		for j := 0; j <= 3*w; j++ {
			if states[i-1][j] {
				states[i][j] = states[i-1][j]
			}
		}

		// 第i个物品购买
		for j := 0; j < 3*w-items[i]; j++ {
			if states[i-1][j] {
				states[i][j+items[i]] = true
			}
		}
	}

	// 输出结果大于等于w的最小值，minM 的值就是列的坐标
	minM := 0
	for minM = w; minM < 3*w+1; minM++ {
		if states[n-1][minM] {
			break
		}
	}
	// 没有最优解
	if minM == 3*w+1 {
		return -1, nil
	}

	// 找出在最优解的情况下都购买了哪些商品
	j := minM
	result := make([]int, n)
	for i := n - 1; i >= 1; i-- {
		// 判断是否购买了第i个物品
		if j-items[i] >= 0 && states[i-1][j-items[i]] {
			result[i] = 1
			j -= items[i]
		}
	}
	// 第0个物品特殊处理
	if j == items[0] {
		result[0] = 1
	}

	return minM, result
}
